import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.text.*;
import java.util.*;
import java.io.*;

class SecondOrderViterbi extends MarkovModelAlgo {

	  double[][] v;
	  SecondOrderTraceback[][] B;
	  SecondOrderTraceback B0;

	  public SecondOrderViterbi(SecondOrderHMM hmm, Object x[]) {
	    super(hmm, x);
	    final int L = x.length;
	    v = new double[L+1][hmm.nstate];
	    B = new SecondOrderTraceback[L+1][hmm.nstate];
	    v[0][0] = 0;
	    for (int k=1; k<hmm.nstate; k++) v[0][k] = Double.NEGATIVE_INFINITY;
	    for (int i=1; i<=L; i++) v[i][0] = Double.NEGATIVE_INFINITY;
	    for (int i=1; i<=L; i++) for (int ell=0; ell < hmm.nstate; ell++) {
	        int kmax = 0;
		int jmax = 0;
	        double maxprod = v[i-1][kmax] + hmm.loga[jmax][kmax][ell];
	        for (int j=1; j<hmm.nstate; j++) for (int k=1; k<hmm.nstate; k++) {
	          double prod = v[i-1][k] + hmm.loga[j][k][ell];
	          if (prod > maxprod) {
	            kmax = k;
	            jmax = j;
	            maxprod = prod;
	          }
	        }
	        v[i][ell] = hmm.loge[ell][hmm.getSym(x[i-1])] + maxprod;
	        B[i][ell] = new SecondOrderTraceback(i-1, jmax, kmax);
	    }
	    int kmax = 0;
	    double max = v[L][kmax];
	    for (int k=1; k<hmm.nstate; k++) {
	      if (v[L][k] > max) {
	        kmax = k;
	        max = v[L][k];
	      }
	    }
	    B0 = new SecondOrderTraceback(L, 0, kmax);
	  }
	  
	  public Object[] getPath() {
	    List<Object> res = new ArrayList<Object>();
	    SecondOrderTraceback tb = B0;
	    int i = tb.i, j = tb.j, k = tb.k;
	    while ((tb = B[tb.i][tb.k]) != null) {
	      res.add( ((SecondOrderHMM)mm).state[k] );
	      i = tb.i; 
	      j = tb.j;
	      k = tb.k;
	    }
	    Collections.reverse(res);
	    return res.toArray(new Object[0]);
	  }

	  public void print(PrintStream out) {
	    int nstate = ( mm instanceof HMM ) ? ((HMM)mm).nstate : 1;
	    for (int j=0; j<nstate; j++) {
	      for (int i=0; i<v.length; i++) out.print(MarkovModel.fmtlog(v[i][j]));
	      out.println();
	    }
	  }

}
